package com.zjj.algorithm.learning.leetcode.tree;

/**
 * 104. 二叉树的最大深度 简单题
 * 给定一个二叉树，找出其最大深度。
 * <p>
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * @author zjj_admin
 * @date 2022/11/22 10:52
 */
public class MaximumDepthOfBinaryTree {

    public static void main(String[] args) {


        /**
         *                  node1
         *             node2    node3
         *                    node4
         *                 node5
         *             node6  node7
         */
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node1.left = node2;
        node1.right = node3;
        node3.left = node4;

        node4.left = null;
        node5.left = node6;
        node5.right = node7;
        int res = maxDepth(node1);
        System.out.println("res = " + res);

    }

    /**
     * 思路：从下向上递归
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 41.1 MB
     * 击败
     * 67.53%
     *
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            //获取左子树的深度
            int leftLen = maxDepth(root.left);
            //获取右子树的深度
            int rightLen = maxDepth(root.right);
            //深度去最大值
            int max = Math.max(leftLen, rightLen);
            return max + 1;
        }
    }

    /**
     * 求叶子节点的最大深度
     *
     * @param root
     * @return
     */
    public static int maxDepth3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        if (root.left != null && root.right != null) {
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
        if (root.left != null) {
            return maxDepth(root.left) + 1;
        }
        return maxDepth(root.right) + 1;
    }


    /**
     * 从上到下遍历，未实现
     *
     * @param root
     * @return
     */
    public static int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int max = 1;
        int maxLeft = max;
        int maxRight = max;
        if (root.left != null) {
            maxLeft = getMax(root, root.left, max + 1);
        }
        if (root.right != null) {
            maxRight = getMax(root, root.right, max + 1);
        }
        return Math.max(maxLeft, maxRight);
    }

    private static int getMax(TreeNode node, TreeNode child, int len) {
        if (child.left == null && child.right == null) {
            return 0;
        }
        if (child.left != null) {
        }
        return 0;
    }


}
